package 树;
/**
 * https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/
 */
public class _889_根据前序和后序遍历构造二叉树 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    /*
        1、首先把前序遍历结果的第一个元素或者后序遍历结果的最后一个元素确定为根节点的值。

        2、然后把前序遍历结果的第二个元素作为左子树的根节点的值。

        3、在后序遍历结果中寻找左子树根节点的值，从而确定了左子树的索引边界，进而确定右子树的索引边界，递归构造左右子树即可。
     */
    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        return build(preorder,0, preorder.length-1,
                     postorder,0,postorder.length-1);
    }

    private TreeNode build(int[] preorder,int preStart,int preEnd,
                           int[] postorder,int postStart,int postEnd){
        if(preStart > preEnd) return null;

        //当元素只剩一个的时候，直接返回构造根节点
        //因为下面的逻辑都是在判断节点大于等于2的时候
        if(preStart == preEnd){
            return new TreeNode(preorder[preStart]);
        }

        //将前序遍历的第一个元素当作根节点
        int rootVal = preorder[preStart];
        //将前序遍历的第二个元素当做左子树的根节点
        int leftRootVal = preorder[preStart+1];
        int index = -1; //记录后序遍历中左子树根节点的索引
        for(int i=postStart;i<=postEnd;++i){
            if(leftRootVal == postorder[i]){
                index = i;
                break;
            }
        }
        //后序遍历为 左 右 根，所以左子树的根节点就在后序遍历的最后一个索引
        //根据后序遍历的索引，可以计算出左子树的元素个数
        int leftSize = index - postStart + 1;

        //构造根节点
        TreeNode root = new TreeNode(rootVal);

        root.left = build(preorder,preStart+1,preStart+leftSize,
                          postorder,postStart,index);

        root.right = build(preorder,preStart+leftSize+1,preEnd,
                           postorder,index+1,postEnd -1);

        return root;
    }
}
